package com.njupt.DynamicProgramming;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/21 21:15
 * @Description: 121. 买卖股票的最佳时机
 * @Version: 1.0
 */


public class MaxProfit1_121 {

    /**
     * 法一：暴力法
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        if(prices.length == 1){
            return 0;
        }
        int maxProfit = Integer.MIN_VALUE;

        for (int i = 0; i < prices.length-1; i++) {
            int curMax = 0;
            for (int j = i+1; j < prices.length; j++) {
                if(prices[j] > prices[i]){
                    int profit = prices[j] - prices[i];
                    if(profit > curMax){
                        curMax = profit;
                    }
                }
            }
            if(curMax > maxProfit){
                maxProfit = curMax;
            }
        }
        return maxProfit;
    }

    /**
     * 法二：贪心法
     * 遍历数组中的每个元素（数组中的每个元素表示当天股票票卖出的价格），同时计算之前沟谷股票的最小价格
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        int low = Integer.MAX_VALUE;
        int result = 0;
        for (int i = 0; i < prices.length; i++) {
            low = Math.min(low,prices[i]);
            result = Math.max(result,prices[i] - low);
        }
        return result;
    }

    /**
     * 动态规划
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {

        int dp[][] = new int[prices.length][2];
        dp[0][0] = 0 - prices[0];  //第0天持有了股票
        dp[0][1] = 0;              //第0天不持有股票

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],0 - prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i]);
        }
        return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);
    }

    public static void main(String[] args) {
        MaxProfit1_121 test = new MaxProfit1_121();
        int[] prices = {7,1,5,3,6,4};
        System.out.println(test.maxProfit(prices));

    }
}
